package leetcode.editor.cn;

/**
题目名字---:搜索二维矩阵
题目编号---:74	
解题时间---:2021-09-23 21:47:09
*/

public class SearchA2dMatrix{
    public static void main(String[] args) {
        Solution solution = new SearchA2dMatrix().new Solution();
        int [][] arr = {
                {1,2,3},
                {4,5,6}
        };
        new SearchA2dMatrix().searchMatrix2(arr,5);
        System.out.println(arr.length);

        System.out.println(arr[0].length);
    }

    /**
     * 方法一:暴力法
     * 时间复杂度：n
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix1(int[][] matrix, int target) {
        boolean flag=false;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j]==target) {
                    flag=true;
                    break;
                }
            }
        }
        return flag;
    }

    /**
     * 二分搜索法  m*n矩阵
     * 二维数组展开之后的元素下标: row 行号  col列号
     *  index =(row+1)matrix.length + col
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix2(int[][] matrix, int target) {
        if (matrix.length==0)
            return false;
        int m = matrix.length; //行数
        int n = matrix[0].length; //列数
        int left =0,right=m*n-1;
        while (left<=right) {
            int mid = (left+right)/2;
            int temp = matrix[mid / m - 1][mid % n];
            if (temp==target) {
                return true;
            }
            if (temp>target) {
                right = mid-1;
            }
            if (temp<target) {
                left = mid+1;
            }
        }
        return false;
    }
    
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length==0)
            return false;
        int m = matrix.length; //行数
        int n = matrix[0].length; //列数
        int left =0,right=m*n-1;
        while (left<=right) {
            int mid = (left+right)/2;
            //重点
            int temp = matrix[mid / n ][mid % n];
            if (temp==target) {
                return true;
            }
            if (temp>target) {
                right = mid-1;
            }
            if (temp<target) {
                left = mid+1;
            }
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


}